import org.thymeleaf.expression.Arrays;

import java.util.ArrayList;
import java.util.List;

public class MinimumTotalAlgorithm {

    /**
     * \给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
     * <p>
     * 例如，给定三角形：
     * <p>
     * [
     * [2],
     * [3,4],
     * [6,5,7],
     * [4,1,8,3]
     * ]
     * 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
     * <p>
     * 说明：
     * <p>
     * 如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/triangle
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */

    public static void main(String[] args) {
        MinimumTotalAlgorithm minimumTotalAlgorithm = new MinimumTotalAlgorithm();
        ArrayList<List<Integer>> triangle = new ArrayList<>();
        ArrayList<Integer> integers = new ArrayList<>();
        integers.add(-1);
        triangle.add(integers);
        ArrayList<Integer> integers1 = new ArrayList<>();
        integers1.add(2);
        integers1.add(3);
        triangle.add(integers1);
        ArrayList<Integer> integers2 = new ArrayList<>();
        integers2.add(1);
        integers2.add(-1);
        integers2.add(-3);
        triangle.add(integers2);
//        ArrayList<Integer> integers3 = new ArrayList<>();
//        integers3.add(4);
//        integers3.add(1);
//        integers3.add(8);
//        integers3.add(3);
//        triangle.add(integers3);
        int minimumTotal = minimumTotalAlgorithm.minimumTotalMax(triangle);
        System.out.println("输出:" + minimumTotal);
    }


    public int minimumTotal(List<List<Integer>> triangle) {
        int total = 0;
        int minIndex = 0;
        List<Integer> integerList = triangle.get(0);
        for (int j = 0; j < integerList.size(); j++) {
            if (integerList.get(minIndex) > integerList.get(j)) {
                minIndex = j;
            }
        }
        total = integerList.get(minIndex);
        for (int i = 1; i < triangle.size(); i++) {
            List<Integer> integers = triangle.get(i);
            for (int j = 0; j < integers.size(); j++) {
                if (integers.get(minIndex) > integers.get(j)) {
                    minIndex = j;
                }
            }
            total += integers.get(minIndex);
        }

        return total;
    }


    public int minimumTotalMax(List<List<Integer>> triangle) {
        int row = triangle.size();
        int[] minlen = new int[row+1];
        for (int level = row-1;level>=0;level--){
            for (int i = 0;i<=level;i++){   //第i行有i+1个数字
                minlen[i] = Math.min(minlen[i], minlen[i+1]) + triangle.get(level).get(i);
            }
        }
        return minlen[0];
    }

}
